The invention relates generally to content addressable memory (CAM) devices, and more specifically, to the design and use of a CAM circuit having a plurality of cascaded sub-entries, each sub-entry having a Match-enabled output adapted to enable the CAM search operation of the next sub-entry.
A Content Addressable Memory (CAM) is a device adapted to perform fast searches of list-based data stored in a plurality of locations called CAM entries. Each CAM entry stores a word (i.e., a plurality of binary or ternary bits) of data in a plurality of CAM cells, and includes circuits to perform comparisons with an externally asserted comparand word typically stored in a comparand buffer.
In many CAM circuits of the related art, all of the CAM cells of a given CAM entry are tied directly to the same Match Line (ML) and share a single distributed Match Line Pass-Gate (i.e., the sum of all XNOR circuitry of all the CAM cells in that Match Line""s CAM entry) which performs the logical comparison function and which is connected between the Match Line and a Low voltage level.
The Match Line of a CAM entry functions as a single capacitor having capacitance (CML) that is pre-charged (e.g., through pre-charge transistor) to a logic High voltage (e.g., Vdd) prior to each search, and the observable event on each Match Line will be a MISS (the logical opposite of a MATCH which may be called a HIT), which will cause the Match Line voltage to drop (discharge towards ground voltage) from the pre-charged High voltage to a Low voltage through the Match Line Pass-Gate.
In the CAM arrays of the related art, as the size (i.e., width X) of the binary word storable in each CAM entry is increased, the capacitance (CML) of each CAM entry""s Match Line generally increases proportionately. Thus, in the related art, the Match-sensing hardware designer is faced with the problem of reliably detecting the much smaller and slower voltage change on a Match Line having a potentially large and entry-width-dependent capacitance. Accurate Match-detection requires a circuit to distinguish between the characteristics of a MATCH-ing entry from the characteristics of a MISS-ing entry having as few as only one mismatched data bit (i.e., providing only one conducting leg in the Match Line Pass Gate through which to discharge the Match Line capacitor to the Low voltage). The larger the Match Line""s capacitance (CML), the longer it will take to discharge in the case of a MISS-ing entry, in turn requiring a longer detection period. This generally requires customized sensing circuitry tailored for a specific CAM entry width, and therefore limits the scalability of the CAM circuits of the related art. And, the larger the CAM entry, the greater is the challenge to the designer to define reliable strobing protocols and sensing margins necessary to activate a reliable MATCH or HIT output signal, while maximizing the search frequency. Because only one search at a time can be performed on a CAM entry having one Match Line, the maximum frequency of CAM search operations generally decreases as the width of the CAM entry is increased.
Since the energy consumed (ECAP) by the complete discharge of a capacitor (e.g., a Match Line) is equal to xc2xdCVcap2, where C is the capacitance and Vcap is the Voltage across the capacitor, the energy consumed per search by each MISS (e.g., EMISS=ECAP) with single Match Line systems can increase approximately proportionally with the increased size (bits) of the word storable in the CAM entry. Match Lines in wider CAM entries have larger capacitance associated with them and will therefore consume more power during a search operation and have lower search frequency.
The explosive growth and increasing speed of Intranets and the Internet is fueling the demand for larger, faster, and more energy-efficient CAM circuits. The large CAM memory arrays of the related art can consume multiple watts of power during performance of search operations. It is desirable that the entry-width of CAM arrays may be increased without additional power consumption and/or without reducing the CAM search frequency significantly. A growable CAM architecture (e.g., a data word-width scalable CAM circuit architecture) is desirable for reducing the burdens on circuit designers when implementing wider CAM circuits.
The present invention overcomes the problems and limitations of the related art by providing a cascadable CAM sub-entry architecture based on CAM blocks, and a plurality of exemplary circuits for gating match line segments within CAM blocks, and methods of selecting and combining these blocks to obtain power-savings and/or high performance.
It is desirable that a wide CAM array will consume only minimal energy during operation, and operate at a high speed and/or at a high CAM search frequency, and that each CAM search will reliably generate a Match/HIT output for only CAM entries storing a MATCH-ing word. Accordingly, a first aspect of the invention provides a content addressable memory (CAM) device comprising: a first CAM block having a binary first block input and a binary first block output and including a first sub-entry. The first sub-entry includes one or more CAM cells, each CAM cell in the first sub-entry being coupled to a first match line segment and to a first search-enabling line segment. The device further comprises a first combinatorial logic gate having a binary first gate output and a first gate input, the first gate input being the first match line segment, the first gate output being the first block output. A CAM comparison is performed on the first sub-entry only if a predetermined binary logic voltage level is being asserted at the binary first block input. The first block output will assert the predetermined binary logic voltage level if the first sub-entry is a match-ing sub-entry.
A second aspect of the invention provides a content addressable memory array comprising a plurality of CAM entries, each CAM entry being segmented into first, second and third sub-entries, the first, second and third sub-entries including a first, second and third match-line segment respectively. The first match-line segment is operatively coupled to the second match-line segment through a first combinatorial logic gate, the second match-line segment is operatively coupled to the third match-line segment through a second combinatorial logic gate.
A third aspect of the invention provides a digital system, such as for example, a computer, or a network router, comprising a digital processor operatively coupled to a CAM array, the CAM array having cascaded CAM blocks, as in the forgoing aspects of the invention.
A fourth aspect of the invention provides an ASIC library comprising an ASIC library element having electrical rules that describe devices within and describe interconnections between the devices within a CAM block in accordance with embodiments of the invention.
A fifth aspect of the invention provides a method of performing a CAM comparison on a CAM entry, the method comprising: providing a first CAM block including a binary first block input, a binary first block output, a first CAM cell, the first CAM cell being operatively coupled to the first block input and to the first block output; and performing a CAM comparison on the first CAM cell only if a predetermined binary logic voltage level is asserted at the binary first block input; and asserting the predetermined binary logic voltage level at the first block output.
A sixth aspect of the invention provide a method of performing a CAM comparison on a CAM entry having a first sub-entry and a second sub-entry, the method comprising: providing a first CAM block having a binary first block input and a binary first block output and including the first sub-entry, the first sub-entry having one or more CAM cells; performing a CAM comparison on the first sub-entry only if a predetermined binary logic voltage level is being asserted at the binary first block input; asserting the predetermined binary logic voltage level at the first block output if the CAM comparison on the first sub-entry detects a MATCH-ing sub-entry; providing a second CAM block having a binary second block input and a binary second block output, wherein the first block output is the second block input, and the second CAM block includes the second sub-entry, the second sub-entry having one or more CAM cells; performing a CAM comparison on the second sub-entry only if the predetermined binary logic voltage level is being asserted at the binary second block input; asserting the predetermined binary logic voltage level at the second block output if the CAM comparison on the second sub-entry detects a MATCH-ing sub-entry.
Each CAM block contains a sub-entry, a match line segment, and a match line sensing and gating circuit (e.g., an AND-gate) to control CAM search timing and CAM block output. A plurality of CAM blocks are cascaded (i.e., coupled serially) such that the output of each serves as an input for the next. The output of each CAM block containing a sub-entry may be connected in series with the input of another CAM block containing the next sub-entry, to create a large CAM entry of any desired width. A given sub-entry (after the first sub-entry) is compared to its respective portion of the comparand only if the previous sub-entry was a MATCH-ing sub-entry with respect to its respective portion of the comparand.
Each sub-entry is basically a short CAM entry that has a correspondingly short Match Line (a match line segment) with a relatively small capacitance. Each CAM entry includes a plurality of sub-entries, and therefore, a plurality of Match Line segments. Each CAM block has a search-enabling input and also an output. The plurality of CAM blocks are cascaded (i.e., coupled serially) such that the output of each serves as an input for the next which inhibits or enables the CAM comparison function within CAM sub-entry contained within the block. Each CAM block also has an output to indicate the result of a CAM search comparison on the portion of the entry contained within that block.
Each one of the plurality of match line segments in a given CAM entry is coupled directly to the respective comparison circuit (e.g., XNOR function) of the CAM cells within its respective sub-entry and is further coupled (through a combinatorial logic gate, e.g., an AND gate or a NAND gate) to the match line segment (ML) and search enabling lines (SE) of each adjacent (i.e., next) sub-entry. A word stored in an entry that xe2x80x9cmatchesxe2x80x9d the comparand, results in maintaining the pre-charged High voltage on the match line segment of every sub-entry within such an entry and consequently the output of each CAM block and the HIT output line voltage (VHL) of that CAM cascade is a logic High (i.e., True) voltage level. Conversely, all entries that contain even a single bit that mis-matches (i.e., does not logically match) a comparand""s corresponding bit results in a HIT output of a Low voltage (i.e., False). It would be apparent to persons skilled in the art that the (High-Low; positive-negative) electrical polarity of signals and of elements may be reversed at some or all portions of the circuit without departing from the teachings and scope of the claims of the herein disclosed invention.